/**
 * @param {number[]} prices
 * @return {number}
 */
 var maxProfit = function(k,prices) {
  // 这个股票在某一天有五中状态
  // 0 没有操作 1 第一次买入 2 第一次卖出 3 第二次买入 4 第二次卖出
  if(prices.length === 0) return 0
  let len = prices.length
  let dp = new Array(len).fill(0).map(()=>new Array(2*k+1).fill(0))
  // 初始化 dp[0][0] 就是没有操作就是0
  // dp[0][1] 就是第一次买入 就是 0 - prices[0]
  // dp[0][2] 就是第一次卖出  相当于买入又卖出 相当于0
  // dp[0][3] 第二次买入 相当于 买入卖出又买入 0 - prices[0]
  // dp[0][4] 第二次卖出 相当于 买入有卖出又买入有卖出 0
  for (let j = 1; j < 2 * k; j += 2) {
    dp[0][j] = -prices[0];
  }
  let flag = null
  for(let i = 1;i < len;i++){
    dp[i][0] = dp[i-1][0] // 这一层没操作的状态就是上一次没操作的状态
    for(let j = 1;j < 2*k+1;j++){
      if(j % 2 === 0) {
        flag = 1
      }else{
        flag = -1
      }
      dp[i][j] = Math.max(dp[i-1][j-1] + flag * prices[i],dp[i-1][j])
    }
    
    // dp[i][1] = Math.max(dp[i-1][0] - prices[i],dp[i-1][1]) // 这一次的第一次买入相当于上一次的第一次买入没有操作 和上一次没有操作这次买入
    // dp[i][2] = Math.max(dp[i-1][1] + prices[i],dp[i-1][2]) // 这一次的相当于第一次的买入然后再卖出 或者是第一次的卖出没有操作
    // dp[i][3] = Math.max(dp[i-1][2] - prices[i],dp[i-1][3])
    // dp[i][4] = Math.max(dp[i-1][3] + prices[i],dp[i-1][4])
  }
  return dp[len-1][2*k]
};